#include "hash.h"

/*
 * Aloca um hash na memoria
 * Parametros:
 *  set: hash a ser alocado
 *  tamanho: tamanho do hash a ser alocado
*/
void criar_hash_set(hash_set *set, int tamanho){
	int i;

  /* aloca o vetor de palavras do hash */
	set->set_palavras = (char **)malloc(sizeof(char *) * tamanho);
	
	/* aloca o vetor de palavras maes */
	set->maes = (int **)malloc(sizeof(int *) * tamanho);
	
	/* aloca o vetor de flags que indicam que as palavras foram encontradas */
	set->encontrada = (int *)malloc(sizeof(int) * tamanho);
	
	/* aloca o vetor de contadores de palavras maes */
	set->cnt_maes = (int *)malloc(sizeof(int) * tamanho);
	
	/* inicia o tamanho, o numero de palavras inseridas e o numero de colisoes*/
	set->tamanho = tamanho;
	set->n_palavras = 0;
	set->n_colisoes = 0;

  set->n_encontradas = 0;

  /* inicia os elementos dos vetores de palavras, de flags de palavras encontradas, de palavras maes e de contadores de palavras maes */
	for(i = 0; i < tamanho; ++i){
		set->set_palavras[i] = NULL;
		set->encontrada[i] = 0;
		set->maes[i] = NULL;
		set->cnt_maes[i] = 0;
	}
}

/*
 * Funcao hash (determina em que posicao do hash uma palavra deve ser colocada )
 * Essa funcao e chamada de djb2 e foi retirada de: http://www.cse.yorku.ca/~oz/hash.html
 * Parametros:
 *  set: hash set para o qual a funcao sera calculada
 *  str: palavra sobre a qual a funcao sera calculada
 * Retorno: 
 *  valor da funcao hash
*/
int fhash(hash_set *set, char *str){
	unsigned long hash = 5381;
	int c;

	while(c = *str++){
		hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
	}

  /* retorna o valor da funcao hash mod o tamanho do hash */
	return(hash % set->tamanho);
}

/*
 * Insere uma palavra no hash set
 * Parametros:
 *  set: hash set no qual sera inserida a palavra
 *  str: palavra a ser inserida
 * Retorno:
 *  retorna 1 se a palavra foi inserida e 0 caso contrario
*/
int inserir_hash_set(hash_set *set, char *str){
	int hash = fhash(set, str); /* calcula a funcao hash da palavra */

  /* se ja houver alguem na possicao dada pela funcao hash (houve colisao ou a palavra ja foi inserida) */
	if(set->set_palavras[hash] != NULL){
		/* busca pela palavra ou por uma posicao vazia para inserir */
		do{
		  /* caso a palavra ja tenha sido inserida retorna 0 */
			if(strcmp(set->set_palavras[hash], str) == 0){
				return 0;
			}
			hash = (hash + 1) % set->tamanho; 
		}while(set->set_palavras[hash] != NULL);
		/* se a palavra nao esta no hash houve uma colisao e sera feita a insercao em outra posicao do hash */
		++(set->n_colisoes);
	}

  /* insere a palavra */
  /* aloca a palavra no hash */
	set->set_palavras[hash] = (char *)malloc(sizeof(char) * (strlen(str) + 1));
	/* copia a palavra */
	strcpy(set->set_palavras[hash], str);
	/* incrementa o contador de palavras */
	++(set->n_palavras);

  /* retorna 1 porque a palavra foi inserida */
	return 1;
}

/*
 * Insere uma palavra no hash set com a referencia a uma palavra mae
 * Parametros:
 *  set: hash set no qual sera inserida uma palavra
 *  str: palavra a ser inserida
 *  mae: id da palavra mae
 * Retorno:
 *  retorna 1 se a palavra foi inserida ou se ela ja estava no hash mas a palavra mae atual nao estava em sua lista, ou 0 se ela ja estava no hash e a palavra mae ja era mae da mesma
*/
int inserir_hash_set_mae(hash_set *set, char *str, int mae){
	int hash = fhash(set, str); /* calcula a funcao hash da palavra */

  /* se ja houver alguem na possicao dada pela funcao hash (houve colisao ou a palavra ja foi inserida) */
	if(set->set_palavras[hash] != NULL){
		/* busca pela palavra ou por uma posicao vazia para inserir */
		do{
		  /* caso a palavra ja tenha sido inserida e a mae ja esta na lista retorna 0 */
			if(strcmp(set->set_palavras[hash], str) == 0){
			  if(set->maes[hash][set->cnt_maes[hash] - 1] == mae){
			    return 0;
			  }
			  /* se a palavra ja estiver inserida mas a palavra mae nao estiver na lista */
			  set->maes[hash][set->cnt_maes[hash]] = mae; /* adiciona a palavra mae a lista */
			  ++(set->cnt_maes[hash]); /* incrementa o numero de palavras maes */
				return 1;
			}
			hash = (hash + 1) % set->tamanho; 
		}while(set->set_palavras[hash] != NULL);
		/* se a palavra nao esta no hash houve uma colisao e sera feita a insercao em outra posicao do hash */
		++(set->n_colisoes);
	}

  /* insere a palavra */
  /* aloca a palavra no hash */
	set->set_palavras[hash] = (char *)malloc(sizeof(char) * (strlen(str) + 1));
	strcpy(set->set_palavras[hash], str);

  /* aloca o vetor de palavras maes para a nova palavra */
  set->maes[hash] = (int *)malloc(100 * sizeof(int));
  
  /* insere a palavra mae no vetor */
  set->maes[hash][set->cnt_maes[hash]] = mae; 
	++(set->cnt_maes[hash]);	

	++(set->n_palavras);

	return 1;
}

/*
 * Converte o hash set em um string com as palavras separadas por um espaco
 * Parametros:
 *  set: hash set a ser convertido
 * Retorno:
 *  string na qual o hash foi convertido
*/
char *hash_set_para_string(hash_set *set){
  char *str;
	int cnt_set, tamanho_set = set->tamanho, tamanho_str = 0;
	
	/* conta o tamanho da string de retorno */
	for(cnt_set = 0; cnt_set < tamanho_set; ++cnt_set){
	  /* se aquela posicao da lista de palavra esta ocupada o seu tamanho e contado */
		if(set->set_palavras[cnt_set] != NULL){
		  tamanho_str += strlen(set->set_palavras[cnt_set]) + 1;
		}
	}
	
	/* aloca a string de retorno */
	str = (char *)malloc(tamanho_str * sizeof(char));
	
	/* copia as palavras para a string de retorno */
	tamanho_str = 0;
	for(cnt_set = 0; cnt_set < tamanho_set; ++cnt_set){
	  /* se a posicao do hash esta ocupada (ha uma palavra nessa posicao) */
		if(set->set_palavras[cnt_set] != NULL){
      strcpy(&str[tamanho_str], set->set_palavras[cnt_set]); /* copia a palavra para a string de retorno */
      tamanho_str += (strlen(set->set_palavras[cnt_set])); /* incrementa o tamanho da palavra */
      str[tamanho_str] = ' ';
      ++tamanho_str;
		}
	}
	str[tamanho_str - 1] = '\0'; /* fecha string */

	return str;
}

/*
 * Encontra uma palavra no hash set
 * Parametros:
 *  set: hash set onde sera buscada a palavra
 *  str: palavra a ser procurada
 *  encontradas: ids das maes das palavras encontradas
 * Retorno:
 *  numero de maes da palavra encontrada ou 0 caso a palavra nao seja encontrada
*/
int encontrar_hash_set(hash_set *set, char *str, int **encontradas){
	int hash = fhash(set, str); /* valor da funcao hash para a palavra sendo buscada */

  /* se nao ha palavra na posicao calcula entao a palavra nao esta no hash */
	if(set->set_palavras[hash] != NULL){
	  /* se ha palavra nessa posicao entao a palavra pode estar no hash e a mesma sera buscada */
		do{
		  /* se a a palavra foi encontrada */
			if(strcmp(set->set_palavras[hash], str) == 0){
			  /* se a palavra ja nao tiver sido econtrada */
			  if(set->encontrada[hash] == 0){
			    set->encontrada[hash] = 1; /* marca a mesma como encontrada */
			    ++(set->n_encontradas);
				  (*encontradas) = set->maes[hash]; /* seta o parametro de retorno com as maes da palavra */
				  return set->cnt_maes[hash]; /* retorna o numero de maes */
				}
				/* se a palavra ja foi encontrada retorna 0 */
				return 0;
			}
			hash = (hash + 1) % set->tamanho; 
		}while(set->set_palavras[hash] != NULL);
	}

	return 0;
}

/*
 * Deleta um hash set
 *  set: hash set a ser deletado
*/
void deletar_hash_set(hash_set *set){
	int i, tamanho = set->tamanho;

  /* deleta o vetor de encontradas */
  free(set->encontrada);

  /* deleta as palavras e os vetores de ids de maes */
	for(i = 0; i < tamanho; ++i){
		free(set->set_palavras[i]);
		free(set->maes[i]);
	}

  free(set->maes);
	free(set->set_palavras);
}

